package offer_test_20;

import struct.LinkedNode;

//：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
public class seventeen_MergeSortedLists {
	public static void main(String[] args) {
		LinkedNode head = new LinkedNode();
		LinkedNode second = new LinkedNode();
		LinkedNode third = new LinkedNode();
		LinkedNode four = new LinkedNode();
		head.next = second;
		second.next = third;
		third.next = four;
		head.data = 1;
		second.data = 2;
		third.data = 3;
		four.data = 4;

		LinkedNode head1 = new LinkedNode();
		LinkedNode second1 = new LinkedNode();
		LinkedNode third1 = new LinkedNode();
		LinkedNode four1 = new LinkedNode();
		head1.next = second1;
		second1.next = third1;
		third1.next = four1;

		head1.data = 2;
		second1.data = 4;
		third1.data = 6;
		four1.data = 8;
		System.out.println((int) head1.data > (int) head.data);
		LinkedNode rs = mergesort2(head1, head);
		while (rs != null) {
			System.out.println(rs.data);
			rs = rs.next;
		}

	}

	// 非递归
	public static LinkedNode mergesort(LinkedNode one, LinkedNode two) {
		LinkedNode rs = new LinkedNode();
		while (one != null || two != null) {
			if (one != null) {
				// System.out.println(one.data+"  "+ two.data);
				if (two != null && (int) one.data < (int) two.data) {
					rs = insert(rs, one);
					one = one.next;
				}
				if (two == null) {
					rs = insert(rs, one);
					one = one.next;
				}
			}
			if (two != null) {
				if (one != null && (int) one.data >= (int) two.data) {
					rs = insert(rs, two);
					two = two.next;
				}
				if (one == null) {
					rs = insert(rs, two);
					two = two.next;
				}
			}
		}

		return rs;
	}

	public static LinkedNode insert(LinkedNode node, LinkedNode add) {
		LinkedNode now = new LinkedNode();
		now.data = add.data;
		if (node.data == null) {
			node = now;
		} else {
			LinkedNode nn = node;
			while (nn.next != null) {
				nn = nn.next;
			}
			nn.next = now;
		}
		return node;
	}

	// 递归
	public static LinkedNode mergesort2(LinkedNode one, LinkedNode two) {
		if (one == null)
			return two;
		if (two == null)
			return one;
		LinkedNode rs = new LinkedNode();
		if ((int) one.data < (int) two.data) {
			rs = insert(rs, one);
			rs.next = mergesort(one.next, two);
		}
		if ((int) one.data >= (int) two.data) {
			rs = insert(rs, two);
			rs.next = mergesort(one, two.next);
		}
		return rs;
	}
}
